package collectionsUtils;

/**
 * 功能描述: 二分查找
 * 2025/04/23
 *
 * @author ZhangYi
 */
public class HalfFindCollection {

	public static void main(String[] args) {
		int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};

		int target = -11;
		int index = halfFind(arr, target);
		System.out.println(String.format("元素 %s 的索引位置为 %s", target, index));

		arr = new int[]{1, 2, 2, 2, 3, 3, 3, 4, 5, 6};
		target = 3;
		index = halfFindMoreLeftLessEqual(arr, target);
		System.out.println(String.format("元素 %s 的索引位置为 %s", target, index));

		index = halfFindMoreRightGreaterEqual(arr, target);
		System.out.println(String.format("元素 %s 的索引位置为 %s", target, index));

	}


	/**
	 * 二分查找
	 *
	 * @param arr    arr
	 * @param target 目标
	 * @return int
	 * @author ZhangYi
	 */
	public static int halfFind(int[] arr, int target) {
		if (arr == null || arr.length == 0) {
			return -1;
		}

		int L = 0;
		int R = arr.length - 1;

		while (L <= R) {
			int M = (L + R) >> 1;
			if (arr[M] < target) {
				L = M + 1;
			} else if (arr[M] > target) {
				R = M - 1;
			} else {
				return M;
			}

		}
		return -1;

	}

	/**
	 * 一半找到更多左 小于等于
	 * 1,2,2,2,3,3,3,3,4,4,4
	 * target 2  返回索引下标 1
	 *
	 * @param arr    arr
	 * @param target 目标
	 * @return int
	 * @author ZhangYi
	 */
	public static int halfFindMoreLeftLessEqual(int[] arr, int target) {
		if (arr == null || arr.length == 0) {
			return -1;
		}
		int L = 0;
		int R = arr.length - 1;

		int index = -1;
		while (L <= R) {
			int M = (L + R) >> 1;

			if (target <= arr[M]) {
				R = M - 1;
				index = M;
			} else {
				L = M + 1;
			}
		}
		return index;
	}


	/**
	 * 一半找到更多右侧 大于等于
	 * 1,2,2,2,3,3,3,3,4,4,4
	 * target 2  返回索引下标 3
	 *
	 * @param arr    arr
	 * @param target 目标
	 * @return int
	 * @author ZhangYi
	 */
	public static int halfFindMoreRightGreaterEqual(int[] arr, int target) {
		// exit condition;
		if (arr == null || arr.length == 0) {
			return -1;
		}
		int L = 0;
		int R = arr.length - 1;

		int location = -1;

		while (L <= R) {
			int M = (L + R) >> 1;
			if (arr[M] <= target) {
				L = M + 1;
				location = M;
			} else {
				R = M - 1;
			}
		}

		return location;

	}
}
